package MyString;

import java.util.ArrayList;

/**
 * 1358. 包含所有三种字符的子字符串数目
 *
 * 给你一个字符串 s ，它只包含三种字符 a, b 和 c 。
 *
 * 请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "abcabc"
 * 输出：10
 * 解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。
 */
public class Leetcode1358 {
    // 二分查找第一个大于等于目标的数字，不是位置
    public static int myFind(ArrayList<Integer> cnt, int target) {
        int left = 0, right = cnt.size()-1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(cnt.get(mid) == target) {
                return cnt.get(mid);
            } else if(cnt.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if(left >= cnt.size()){
            return -1;
        }
        return cnt.get(left);
    }
    public static int numberOfSubstrings(String s) {
        ArrayList<Integer> cntA= new ArrayList<>();
        ArrayList<Integer> cntB= new ArrayList<>();
        ArrayList<Integer> cntC= new ArrayList<>();

        // 预处理三者的所有位置 O(3*n)
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == 'a'){
                cntA.add(i);
            }else if(s.charAt(i) == 'b'){
                cntB.add(i);
            }else{
                cntC.add(i);
            }
        }

        if(cntA.size()==0 || cntB.size()==0 || cntC.size()==0){
            return 0;
        }

        int res = 0;
        // 计算每一位开始的字符串符合条件的字符串
        for(int i=0; i<= s.length()-3; i++){
            int a_find = myFind(cntA, i);
            int b_find = myFind(cntB, i);
            int c_find = myFind(cntC, i);
            if(a_find!=-1 && b_find!=-1 && c_find!=-1){
                int local_max = Math.max(Math.max(a_find, b_find), c_find);
                res += s.length()-local_max;
            }
        }
        return res;
    }

    //滑动窗口解法
    public static int numberOfSubstrings2(String s) {
        int res = 0;
        int[] cnt = new int[3];
        int start = 0;
        for(int i=0; i<s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
            while(cnt[0] >= 1 && cnt[1]>=1 && cnt[2]>=1){
                //计算start位置开始的符合条件的
                res += (s.length() - i);

                // 去掉最左边的一个字符 滑动窗口
                cnt[s.charAt(start) - 'a']--;
                start ++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String ss = "abacbaaccbbaabc"; //77
        System.out.println(numberOfSubstrings2(ss));
    }
}
